package com.company.单调栈;

import java.util.Stack;

/*
* 每个人分别往右看各自能看见多少人
* 单调栈 依次入栈，能保持单调性的入栈，不能的出栈若干再入栈
* 本质：及时去掉无用的数据
*/
public class LeeCode1944 {
    public int[] canSeePersonsCount(int[] heights) {//思路：i之前的人中，能看见i的举手
        int[] answer=new int[heights.length];//new的数组初值全为0

        Stack<Integer>s=new Stack<Integer>();
        s.push(0);
        for(int i=1;i<heights.length;i++){//1到n-1进出单调栈的过程
            while (!s.empty()){
                answer[s.peek()]++;
                if(heights[i]<heights[s.peek()])break;
                s.pop();
            }
            s.push(i);
        }
        return answer;
    }
}
